package binaryTree;

public class D230720 {
    // 对称二叉树
    public boolean isSymmetrical (TreeNode pRoot) {
        if (pRoot == null) {
            return true;
        }
        // 同时递归左右子树
        return isSymmetrical(pRoot.left, pRoot.right);
    }
    public boolean isSymmetrical(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            // 都为空，对称
            return true;
        }
        if (left == null || right == null || left.val != right.val) {
            // 只有一个为空，或者两个值不相同，不对称
            return false;
        }
        // 继续递归，左左，右右 && 左右，右左
        return isSymmetrical(left.left, right.right) && isSymmetrical(left.right, right.left);
    }

    // 合并二叉树
    // 将 t2 合并到 t1
    public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {
        if (t1 == null || t2 == null) {
            return t1 != null ? t1 : t2;
        }
        t1.val += t2.val;
        if (t1.left == null || t2.left == null) {
            if (t1.left == null) {
                t1.left = t2.left;
            }
        } else {
            mergeTrees(t1.left, t2.left);
        }
        if (t1.right == null || t2.right == null) {
            if (t1.right == null) {
                t1.right = t2.right;
            }
        } else {
            mergeTrees(t1.right, t2.right);
        }
        return t1;
    }
    // 新建一个二叉树 sumTree, 合并t1和t2
    public TreeNode mergeTrees2 (TreeNode t1, TreeNode t2) {
        if (t1 == null || t2 == null) {
            return t1 != null ? t1 : t2;
        }
        TreeNode sumTree = new TreeNode(t1.val + t2.val);
        sumTree.left = mergeTrees2(t1.left, t2.left);
        sumTree.right = mergeTrees2(t2.right, t2.right);
        return sumTree;
    }


    // 二叉树的镜像
    public TreeNode Mirror (TreeNode pRoot) {
        if (pRoot == null) {
            return pRoot;
        }
        TreeNode newTree = new TreeNode(pRoot.val);
        newTree.left = Mirror(pRoot.right);
        newTree.right = Mirror(pRoot.left);
        return newTree;
    }

    // 判断是不是二叉搜索树
    // 二叉搜索数的中序遍历是 递增的
    private TreeNode pre;
    public boolean isValidBST (TreeNode root) {
        if (root == null) return true;

        if (!isValidBST(root.left)) return false;

        if (pre != null && pre.val >= root.val) return false;

        pre = root;

        if (!isValidBST(root.right)) return false;

        return true;
    }
}
